

// #include<iostream>
// #include<vector>

// using namespace std;
// class Solution {
// public:
//    int x = 0, y = 0;
//    bool Search(vector<vector<int>>& vv, string& word, int x,int y,int index)
//    {
//        if (index == word.size()) return true;
//
//        if (vv[x - 1][y] == word[index])  return Search(vv, word, x - 1, y, index + 1);
//        else if (vv[x + 1][y] == word[index]) return Search(vv, word, x + 1, y, index + 1);
//        else if (vv[x][y - 1] == word[index])  return Search(vv, word, x, y - 1, index + 1);
//        else if (vv[x][y + 1] == word[index])  return Search(vv, word, x, y + 1, index + 1);
//        else return false;
//    }
//    bool exist(vector<string>& board, string word) {
//        vector<vector<int>> vv(board.size() + 2, vector<int>(board[0].size() + 2));
//        vector<vector<int>> index;
//        for (int i = 1; i <= board.size(); i++)
//        {
//            for (int j = 1; j <= board[0].size(); j++)
//            {
//                vv[i][j] = board[i - 1][j - 1];
//                if (vv[i][j] == word[0]) index.push_back({ i,j });
//            }
//        }
//        int ret = 0;
//        for (int i = 0; i < index.size(); i++)
//        {
//            ret |= Search(vv, word, index[i][0], index[i][1],1);
//        }
//        return ret;
//    }
//};
// int main()
//{
//	int n = 0;
//	cin >> n;
//	vector<vector<int>> vv(n, vector<int>(n,1));
//	for (int i = 2; i < n; i++)
//	{
//		for (int j = 1; j < i; j++)
//		{
//			vv[i][j] = vv[i-1][j]+vv[i-1][j-1];
//		}
//	}
//
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j <= i; j++)
//		{
//			printf("%-5d", vv[i][j]);
//		}
//		cout << endl;
//	}
//	return 0;
//}
// int main()
//{
//	int n = 0,prev1 = 0,prev2 = 1;
//	cin >> n;
//	int cur = 1;
//	while (cur < n)
//	{
//		prev1 = prev2;
//		prev2 = cur;
//		cur = prev1 + prev2;
//	}
//	int ret = min(cur - n, n - prev2);
//	cout << ret << endl;
//	return 0;
//
// }
